package leetcode.list;

import java.util.HashMap;

public class LRUCache {

    class DLinkedNode {
        DLinkedNode pre;
        DLinkedNode next;
        int val, key;
        public DLinkedNode() {}

        public DLinkedNode(int key, int val) {
            this.val = val;
            this.key = key;
        }
    }

    DLinkedNode head = null, tail = null;
    int size;
    int capacity;
    HashMap<Integer, DLinkedNode> cache;

    public LRUCache(int capacity) {
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.pre = head;
        cache = new HashMap<>();
        size = 0;
        this.capacity = capacity;
    }

    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if (node == null) return -1;
        moveToHead(node);
        return node.val;
    }

    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);
        if (node != null) {
            node.val = value;
            moveToHead(node);
        } else {
            node = new DLinkedNode(key, value);
            cache.put(key, node);
            size++;
            node.next = head.next;
            node.pre = head;
            head.next.pre = node;
            head.next = node;
            if (size > capacity) {
                cache.remove(tail.pre.key);
                remove(tail.pre);
                size--;
            }
        }
    }

    private void moveToHead(DLinkedNode node) {
        remove(node);
        node.next = head.next;
        node.pre = head;
        head.next.pre = node;
        head.next = node;
    }

    private void remove(DLinkedNode node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(2);
        lruCache.put(1,0);
        lruCache.put(2,2);
        lruCache.get(1);
        lruCache.put(3,3);
        lruCache.get(2);
        lruCache.put(4,4);
        System.out.println(lruCache.get(1));


    }
}
